{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Number of Taps to Open to Water a Garden"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minTaps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #灌溉花园的最少水龙头数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在 x 轴上有一个一维的花园。花园长度为&nbsp;<code>n</code>，从点&nbsp;<code>0</code>&nbsp;开始，到点&nbsp;<code>n</code>&nbsp;结束。</p>\n",
    "\n",
    "<p>花园里总共有&nbsp;<code>n + 1</code> 个水龙头，分别位于&nbsp;<code>[0, 1, ..., n]</code> 。</p>\n",
    "\n",
    "<p>给你一个整数&nbsp;<code>n</code>&nbsp;和一个长度为&nbsp;<code>n + 1</code> 的整数数组&nbsp;<code>ranges</code>&nbsp;，其中&nbsp;<code>ranges[i]</code> （下标从 0 开始）表示：如果打开点&nbsp;<code>i</code>&nbsp;处的水龙头，可以灌溉的区域为&nbsp;<code>[i -&nbsp; ranges[i], i + ranges[i]]</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回可以灌溉整个花园的&nbsp;<strong>最少水龙头数目</strong>&nbsp;。如果花园始终存在无法灌溉到的地方，请你返回&nbsp;<strong>-1</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/01/19/1685_example_1.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 5, ranges = [3,4,1,1,0,0]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：\n",
    "</strong>点 0 处的水龙头可以灌溉区间 [-3,3]\n",
    "点 1 处的水龙头可以灌溉区间 [-3,5]\n",
    "点 2 处的水龙头可以灌溉区间 [1,3]\n",
    "点 3 处的水龙头可以灌溉区间 [2,4]\n",
    "点 4 处的水龙头可以灌溉区间 [4,4]\n",
    "点 5 处的水龙头可以灌溉区间 [5,5]\n",
    "只需要打开点 1 处的水龙头即可灌溉整个花园 [0,5] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, ranges = [0,0,0,0]\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>即使打开所有水龙头，你也无法灌溉整个花园。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>ranges.length == n + 1</code></li>\n",
    "\t<li><code>0 &lt;= ranges[i] &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-number-of-taps-to-open-to-water-a-garden](https://leetcode.cn/problems/minimum-number-of-taps-to-open-to-water-a-garden/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-number-of-taps-to-open-to-water-a-garden](https://leetcode.cn/problems/minimum-number-of-taps-to-open-to-water-a-garden/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5\\n[3,4,1,1,0,0]', '3\\n[0,0,0,0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTaps(self, n: int, ranges: List[int]) -> int:\n",
    "        if len(ranges) == 0:\n",
    "            return 0\n",
    "        \n",
    "        max_ranges = [0]*(n+1)\n",
    "           \n",
    "        for i in range(len(ranges)):\n",
    "            left, right =  max(0, i-ranges[i]), min(n, ranges[i]+i)\n",
    "            max_ranges[left] = max(right-left, max_ranges[left])\n",
    "        \n",
    "        nums = max_ranges\n",
    "        taps=0\n",
    "        l = 0\n",
    "        r = nums[l]\n",
    "        \n",
    "        while True:\n",
    "            if r >= len(nums)-1:\n",
    "                return taps + 1\n",
    "            elif l == r:\n",
    "                return -1\n",
    "            cover = nums[r]+r\n",
    "            cover_idx = r\n",
    "            for i in range(l+1, r+1):\n",
    "                if nums[i] + i > cover:\n",
    "                    cover = nums[i]+i\n",
    "                    cover_idx = i\n",
    "            l, r = cover_idx, cover\n",
    "            taps += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTaps(self, n: int, ranges: List[int]) -> int:\n",
    "        M = 1e10 + 5\n",
    "        dp = [M] * 10005\n",
    "        dp[0] = 0\n",
    "        for i in range(n + 1):\n",
    "            l = max(0, i - ranges[i])\n",
    "            r = min(n, i + ranges[i])\n",
    "            j = l\n",
    "            while j <= r:\n",
    "                dp[j] = min(dp[j], dp[l] + 1)\n",
    "                j += 1\n",
    "        return dp[n] if dp[n] != M else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTaps(self, n: int, ranges: List[int]) -> int:\n",
    "        furthest, cnt, cur = [0] * n, 0, 0\n",
    "\n",
    "        for i in range(n + 1):\n",
    "            l = max(0, i - ranges[i])\n",
    "            r = min(n, i + ranges[i])\n",
    "            for j in range(l, r):\n",
    "                furthest[j] = max(furthest[j], r)\n",
    "        while cur < n:\n",
    "            if furthest[cur] == 0: return -1\n",
    "            cur = furthest[cur]\n",
    "            cnt += 1\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTaps(self, n: int, ranges: List[int]) -> int:\n",
    "        #i用于循环，k为使用的个数，初始默认为1\n",
    "        #max_len1记录左边最远，max_len2记录右边最远\n",
    "        i=0\n",
    "        k=1\n",
    "        max_len1=0\n",
    "        max_len2=0\n",
    "        while i<len(ranges):\n",
    "            #遍历所有左边最远超过所需左边界的可能\n",
    "            if i-ranges[i]<=max_len1:\n",
    "                #选出其中右边可以达到最远的距离，记录下来\n",
    "                if i+ranges[i]>max_len2:\n",
    "                    max_len2=i+ranges[i]\n",
    "                    w=i\n",
    "            #如果右边超过右边界，则完成灌溉，返回个数k\n",
    "            if max_len2>=len(ranges)-1:\n",
    "                return k\n",
    "            i+=1\n",
    "            #如果已经遍历过一遍，则确定选择当前最远的max_len2，将其设定为新的左边界\n",
    "            if i==len(ranges):\n",
    "                if max_len2!=max_len1:\n",
    "                    k=k+1\n",
    "                    max_len1=max_len2\n",
    "                    i=0\n",
    "                #如果max_len1与max_len2相等，说明没有找到能继续往下灌溉的水龙头，返回-1\n",
    "                else:\n",
    "                    return -1\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTaps(self, n: int, ranges: List[int]) -> int:\n",
    "        dp = [0] + [n + 2] * n\n",
    "        for i, x in enumerate(ranges):\n",
    "            for j in range(max(i - x + 1, 0), min(i + x, n) + 1):\n",
    "                dp[j] = min(dp[j], dp[max(0, i - x)] + 1)\n",
    "        return dp[n] if dp[n] < n + 2 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTaps(self, n: int, ranges: List[int]) -> int:\n",
    "        land = [0] * n\n",
    "        for i in range(n+1):\n",
    "            l = max(i - ranges[i],0)\n",
    "            r = min(i + ranges[i],n)\n",
    "            for j in range(l,r):\n",
    "                land[j] = max(land[j],r)\n",
    "        count = 0\n",
    "        cur = 0\n",
    "        while cur < n :\n",
    "            if land[cur] == 0 :\n",
    "                return -1\n",
    "            else:\n",
    "                cur = land[cur]\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTaps(self, n: int, ranges: List[int]) -> int:\n",
    "        pour_dis= [0] * (n + 1)\n",
    "        for i, step in enumerate(ranges):\n",
    "            a, b = max(0, i - step), i + step\n",
    "            pour_dis[a] = max(pour_dis[a], b)\n",
    "        ans, max_dis, end = 0, 0, 0\n",
    "        for i in range(n):\n",
    "            max_dis = max(max_dis, pour_dis[i])\n",
    "            if i == end:\n",
    "                end = max_dis\n",
    "                ans += 1\n",
    "        if end >= n:\n",
    "            return ans  \n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTaps(self, n: int, ranges: List[int]) -> int:\n",
    "        prev = [x for x in range(n + 1)]\n",
    "        for i in range(n + 1):\n",
    "            l = max(i - ranges[i], 0)\n",
    "            r = min(i + ranges[i], n)\n",
    "            prev[r] = min(prev[r], l)\n",
    "        \n",
    "        breakpoint, furthest = n, 2**30\n",
    "        ans = 0\n",
    "        for i in range(n, 0, -1):\n",
    "            furthest = min(furthest, prev[i])\n",
    "            if i == breakpoint:\n",
    "                if furthest >= i:\n",
    "                    return -1\n",
    "                breakpoint = furthest\n",
    "                ans += 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTaps(self, n: int, ranges: List[int]) -> int:\n",
    "        left=[i for i in range(n+1)]\n",
    "        for i in range(n+1):\n",
    "            l=max(0, i-ranges[i])\n",
    "            r=min(n, i+ranges[i])\n",
    "            left[r]=min(left[r], l)\n",
    "        dp=[float('inf') for _ in range(n+1)]\n",
    "        dp[0]=0\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(left[i], i):\n",
    "                dp[i]=min(dp[i], dp[j]+1)\n",
    "        return dp[-1] if dp[-1]!=float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTaps(self, n: int, ranges: List[int]) -> int:\n",
    "        memo = []\n",
    "        for i in range(len(ranges)):\n",
    "            memo.append((max(0, i - ranges[i]), i + ranges[i]))\n",
    "        memo.sort(key=lambda s: s[0])\n",
    "        # print(memo)\n",
    "        right = 0\n",
    "        nextRight = 0\n",
    "        cnt = 0\n",
    "        for i in memo:\n",
    "            if i[0] > right:\n",
    "                if i[0] > nextRight:\n",
    "                    return -1\n",
    "                right = nextRight\n",
    "                cnt += 1\n",
    "            if i[1] > nextRight:\n",
    "                nextRight = i[1]\n",
    "            if right >= n:\n",
    "                return cnt\n",
    "        else:\n",
    "            if nextRight >= n:\n",
    "                return cnt + 1\n",
    "            return -1\n",
    "        # return cnt\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    " \n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTaps(self, n: int, ranges: List[int]) -> int:\n",
    "        land=[0]*n\n",
    "        for i in range(n+1):\n",
    "            left=max(0,i-ranges[i])\n",
    "            right=min(n,i+ranges[i])\n",
    "            for j in range(left,right):\n",
    "                land[j]=max(land[j],right)\n",
    "\n",
    "        cnt,pos=0,0\n",
    "        for i in range(n):\n",
    "            if land[i]==0 or pos==land[pos]:\n",
    "                return -1\n",
    "            else:\n",
    "                pos=land[pos]\n",
    "                cnt+=1\n",
    "            if pos==len(ranges)-1:\n",
    "                return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTaps(self, n: int, ranges: List[int]) -> int:\n",
    "        l = 0\n",
    "        res = 0\n",
    "        maxr = 0\n",
    "        flag = False\n",
    "        while True:\n",
    "            # if l >= n:\n",
    "            #     return res - 1\n",
    "            if flag and maxr <= l:\n",
    "                return -1\n",
    "            flag = True\n",
    "            l = maxr\n",
    "            if l >= n:\n",
    "                return res\n",
    "            for i in range(n+1):\n",
    "                # print(i-ranges[i])\n",
    "                if i-ranges[i] <= l:\n",
    "                    maxr = max(maxr, i+ranges[i])\n",
    "                    # print()\n",
    "            # print(maxr)\n",
    "            res += 1\n",
    "            # flag = False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTaps(self, n: int, ranges: List[int]) -> int:\n",
    "\n",
    "        d = [0] * (n + 1)\n",
    "        for i, r in enumerate(ranges):\n",
    "            minn, maxn = max(0, i - r), min(n, i + r)\n",
    "            d[minn] = max(d[minn], maxn)\n",
    "        # print(d)\n",
    "        ans = pre = mr = 0\n",
    "        for i in range(n):\n",
    "            mr = max(mr, d[i])\n",
    "            if i == pre:\n",
    "                pre = mr\n",
    "                ans += 1\n",
    "            if i == mr:\n",
    "                return -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTaps(self, n: int, ranges: List[int]) -> int:\n",
    "        dp = [0] * (n+1)\n",
    "        for k, v in enumerate(ranges):\n",
    "            a, b = max(0, k-v), k+v\n",
    "            dp[a] = max(dp[a], b)\n",
    "        \n",
    "        maxpose = 0\n",
    "        cover = 0\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            maxpose = max(maxpose, dp[i])\n",
    "\n",
    "            if cover == i:\n",
    "                cover = maxpose\n",
    "                res += 1\n",
    "        return res if cover >= n else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTaps(self, n: int, ranges: List[int]) -> int:\n",
    "        rightMost = [i for i in range(n+1)]\n",
    "        for i, r in enumerate(ranges):\n",
    "            left = max(0, i-r)\n",
    "            right = min(n+1, i+r)\n",
    "            rightMost[left] = right\n",
    "            \n",
    "        pre = last = res = 0\n",
    "        for i in range(n):\n",
    "            last = max(last, rightMost[i])\n",
    "            if i == last:\n",
    "                return -1\n",
    "            if i == pre:\n",
    "                res += 1\n",
    "                pre = last\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTaps(self, n: int, ranges: List[int]) -> int:\n",
    "        n += 1\n",
    "        items = sorted(range(n),key = lambda i:i-ranges[i])\n",
    "        ans = 0\n",
    "        mostright = 0\n",
    "        i = 0\n",
    "        while mostright<n-1:\n",
    "            ans += 1\n",
    "            right = mostright\n",
    "            while i<n and items[i]-ranges[items[i]]<=right:\n",
    "                mostright = max(mostright,items[i]+ranges[items[i]])\n",
    "                i += 1\n",
    "            if i == n or mostright == right: break\n",
    "        return ans if mostright>=n-1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTaps(self, n: int, ranges: List[int]) -> int:\n",
    "        dp = [0 for _ in range(n+1)]\n",
    "\n",
    "        for i in range(n+1):\n",
    "            left = max(0, i-ranges[i])\n",
    "            right = min(n, i+ranges[i])\n",
    "            dp[left] = max(dp[left], right-left)\n",
    "\n",
    "        max_pos, end, steps = 0, 0, 0\n",
    "        for i in range(n):\n",
    "            if max_pos >= i:\n",
    "                max_pos = max(max_pos, i+dp[i])\n",
    "                if i == end:\n",
    "                    end = max_pos\n",
    "                    steps += 1\n",
    "        \n",
    "        if max_pos < n:\n",
    "            return -1\n",
    "        \n",
    "        return steps"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTaps(self, n: int, ranges: List[int]) -> int:\n",
    "        rightMost = list(range(n + 1))\n",
    "        for i, r in enumerate(ranges):\n",
    "            start = max(0, i - r)\n",
    "            end = min(n, i + r)\n",
    "            rightMost[start] = max(rightMost[start], end)\n",
    "\n",
    "        last = ret = pre = 0\n",
    "        for i in range(n):\n",
    "            last = max(last, rightMost[i])\n",
    "            if i == last:\n",
    "                return -1\n",
    "            if i == pre:\n",
    "                ret += 1\n",
    "                pre = last\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTaps(self, n: int, ranges: List[int]) -> int:\n",
    "        last = [0] * (n + 1)\n",
    "        for i, x in enumerate(ranges):\n",
    "            l, r = max(0, i - x), i + x\n",
    "            last[l] = max(last[l], r)\n",
    "        ans = mx = pre = 0\n",
    "        for i in range(n):\n",
    "            mx = max(mx, last[i])\n",
    "            if mx <= i:\n",
    "                return -1\n",
    "            if pre == i:\n",
    "                ans += 1\n",
    "                pre = mx\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTaps(self, n: int, ranges: List[int]) -> int:\n",
    "\n",
    "        nex=[0]*(n+1)\n",
    "        for i,v in enumerate(ranges):\n",
    "            nex[max(i-v,0)]=max(nex[max(i-v,0)],min(n,i+v))\n",
    "            \n",
    "        print(nex)\n",
    "        pre=cur=0\n",
    "        count=0\n",
    "        for i in range(n):\n",
    "            cur=max(cur,nex[i])\n",
    "            if cur==i:return -1\n",
    "            if pre==i:\n",
    "                pre=cur\n",
    "                count+=1\n",
    "        \n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTaps(self, n: int, ranges: List[int]) -> int:\n",
    "        # 动态规划 dp[i]表示0-i的花园灌溉的最少水龙头数目\n",
    "        # 将区间按照末尾排序，dp[i]=min(dp[i-k])+1 加入最新区间\n",
    "\n",
    "        MX = 1000000\n",
    "        ends = dict()\n",
    "        for i in range(n+1):\n",
    "            # [i-ranges[i],i+ranges[i]]\n",
    "            e = min(i+ranges[i], n)\n",
    "            if e in ends:\n",
    "                continue\n",
    "            ends[e] = max(i-ranges[i], 0)\n",
    "        dp = [0] + [MX]*n\n",
    "        for i in range(1, n+1):\n",
    "            if i not in ends:\n",
    "                continue\n",
    "            for j in range(ends[i], i):\n",
    "                dp[i] = min(dp[i], dp[j]+1)\n",
    "        return dp[n] if dp[n] < MX else -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTaps(self, n: int, ranges: List[int]) -> int:\n",
    "        ls = []\n",
    "        for i, r in enumerate(ranges):\n",
    "            left = max(0, i - r)\n",
    "            right = min(n, i + r)\n",
    "            ls.append((left, right))\n",
    "        \n",
    "        ls.sort()\n",
    "\n",
    "        f = [inf] * (n + 1)\n",
    "        f[0] = 0\n",
    "\n",
    "        for i, end in ls:\n",
    "            if f[i] == inf:\n",
    "                return -1\n",
    "            for j in range(i, end + 1):\n",
    "                f[j] = min(f[j], f[i] + 1)\n",
    "        \n",
    "        return f[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTaps(self, n: int, ranges: List[int]) -> int:\n",
    "\n",
    "        cand = []\n",
    "        for i, r in enumerate(ranges):\n",
    "            left = max(0, i - r)\n",
    "            right = min(n, i + r)\n",
    "            cand.append((left, right))\n",
    "        cand.sort()\n",
    "\n",
    "        f = [inf] * (n + 1)\n",
    "        f[0] = 0\n",
    "\n",
    "        for left, right in cand:\n",
    "            if f[left] == inf:\n",
    "                return -1\n",
    "            for j in range(left, right + 1):\n",
    "                f[j] = min(f[j], f[left] + 1)\n",
    "        \n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTaps(self, n: int, ranges: List[int]) -> int:\n",
    "        area = [[i-ranges[i],i+ranges[i]] for i in range(len(ranges)) if ranges[i]!=0]\n",
    "        m = len(area)\n",
    "        if m==0: return -1\n",
    "\n",
    "        # 尽量去覆盖，然后看最后有没有全部覆盖\n",
    "        sta = []\n",
    "        # sta[i] = (cl cr) cl cr 表示该area覆盖的区域\n",
    "        i = 0\n",
    "        while i < m:\n",
    "            cur = area[i]\n",
    "            left,right = max(0,cur[0]),min(n,cur[1])\n",
    "            if sta and sta[-1][1]>=right:\n",
    "                i+=1\n",
    "                continue\n",
    "            while sta and left<=sta[-1][0]:\n",
    "                sta.pop(-1)\n",
    "            cl,cr = -1,-1\n",
    "            if len(sta)==0:\n",
    "                cl,cr = max(left, 0),min(right, n)\n",
    "            else:\n",
    "                cl,cr = max(left, sta[-1][1]), min(right,n)\n",
    "            sta.append((cl,cr))\n",
    "            i+=1\n",
    "\n",
    "        if sta[0][0]>0 or sta[-1][1]<n:\n",
    "            return -1\n",
    "        for i in range(len(sta)-1):\n",
    "            if not sta[i][1]==sta[i+1][0]:\n",
    "                return -1\n",
    "        return len(sta)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTaps(self, n: int, ranges: List[int]) -> int:\n",
    "        area = [[i-ranges[i],i+ranges[i]] for i in range(len(ranges)) if ranges[i]!=0]\n",
    "        m = len(area)\n",
    "        if m==0: return -1\n",
    "\n",
    "        # 尽量去覆盖，然后看最后有没有全部覆盖\n",
    "        # cover_points = 0\n",
    "        sta = []\n",
    "        # sta[i] = (idx, cl cr) cl cr 表示该area覆盖的区域\n",
    "        i = 0\n",
    "        while i < m:\n",
    "            cur = area[i]\n",
    "            left,right = max(0,cur[0]),min(n,cur[1])\n",
    "            if sta and sta[-1][2]>=right:\n",
    "                i+=1\n",
    "                continue\n",
    "            while sta and left<=sta[-1][1]:\n",
    "                sta.pop(-1)\n",
    "            cl,cr = -1,-1\n",
    "            if len(sta)==0:\n",
    "                cl,cr = max(left, 0),min(right, n)\n",
    "            else:\n",
    "                cl,cr = max(left, sta[-1][2]), min(right,n)\n",
    "            sta.append((i,cl,cr))\n",
    "            i+=1\n",
    "\n",
    "        if sta[0][1]>0 or sta[-1][2]<n:\n",
    "            return -1\n",
    "        for i in range(len(sta)-1):\n",
    "            if not sta[i][2]==sta[i+1][1]:\n",
    "                return -1\n",
    "        return len(sta)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTaps(self, n: int, ranges: List[int]) -> int:\n",
    "        dp = [inf] * (n + 1)\n",
    "        dp[0] = 0\n",
    "        intervals = []\n",
    "        for i in range(len(ranges)):\n",
    "            start = max(0, i - ranges[i])\n",
    "            end = min(n, i + ranges[i])\n",
    "            intervals.append((start, end))\n",
    "        intervals.sort()\n",
    "\n",
    "        for start, end in intervals:\n",
    "            if dp[start] == inf:\n",
    "                return -1\n",
    "            for j in range(start, end + 1):\n",
    "                dp[j] = min(dp[j], dp[start] + 1)\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTaps(self, n: int, ranges: List[int]) -> int:\n",
    "        \n",
    "        cand = []\n",
    "        for i, r in enumerate(ranges):\n",
    "            left, right = max(0, i - r), min(n, i + r)\n",
    "            cand.append([left, right])\n",
    "        \n",
    "        cand.sort()\n",
    "\n",
    "        f = [inf] * (n + 1)\n",
    "        f[0] = 0\n",
    "\n",
    "        for start, end in cand:\n",
    "            if f[start] == inf:\n",
    "                return -1\n",
    "            for j in range(start, end + 1):\n",
    "                f[j] = min(f[j], f[start] + 1)\n",
    "        \n",
    "        return f[n]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
